// todo: levelbound not accuracy
// todo: lowbound not accuracy
// todo:    cpofsubgraph not accuracy
// todo: unfold issue
// todo: utilize asapuc as asap

//#include "stdafx.h"
#include <stdio.h>
//#include <tchar.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <unistd.h>
// TODO: reference additional headers your program requires here
#include "Graph.h"
#include "HLS.h"
#include "FuncTimer.h"
#include <map>
#include <set>
#include <iostream>
#include <fstream>
#include <time.h>
#include <string>
#include <stdlib.h>
#include <stdio.h>
#include "Graph.h"
#include "FuncTimer.h"
#include "Config.h"
#include <vector>
#include <algorithm>
#include <list>
#include <limits.h>
//#include <boost/thread.hpp>
//#include <boost/thread/thread.hpp
//#include <windows.h>
//#include <direct.h>
#include <pthread.h>
#include <sched.h>
#include <semaphore.h>
//#include "stdafx.h"
using namespace std;
using namespace __gnu_cxx;
//#define INT_MAX 0x7fffffff
// optimization:
// ASAP
// ALAP
// pruning
static bool
operator < (Operation const &op1, Operation const &op2)
{
  return ((op1.sort_id > op2.sort_id));  //|| (op1.sort_id == op2.sort_id && op1.ASAP < op2.ASAP) );
}
int optimalScheduleTime = INT_MAX;
int listSchedulingTime = 0;
listorder global_listorder;
int badScheduleTime = 0;
int basicSchedulingTime = INT_MAX;
int w = INT_MAX;
int level_count = 0;
double GetTickCount(void)
{
  struct rusage ru;
  getrusage(RUSAGE_SELF, &ru);
  return (double)ru.ru_utime.tv_sec + (double)ru.ru_utime.tv_usec / 1000000;
  // struct timespec now;
  //  if (clock_gettime(CLOCK_MONOTONIC, &now))
  //   return 0;
  // return now.tv_sec * 1000.0 + now.tv_nsec / 1000000.0;
}
// resource usage. Records resource usage.
map < type, map < int, int > >resources;
vector < vector < int > * >  history_level_info;
// resource pool.
// Initialized when constructing from test case file.
map < type, int >resourcePool;
// operation pool.
// Initialized when constructing from test case file.
map < int, Operation * >operations;
// constraint pool.
// Initialized when constructing from test case file.
set < Dependency * >dependencies;
// container for current schedule
// Constructed on the fly.
map < Operation *, int >currentSchedule;
// container for best schedule sofar
// Constructed on the fly.
map < Operation *, int >optimalSchedule;
map < Operation *, int >badSchedule;
map < Operation *, int >listingSchedule;
map < Operation *, int >basicSchedule;
map < Operation *, int >lastFeasibleSchedule;
map < Operation *, int >CPofSubGraph;
map < Operation *, int >CPofSubGraph_;
map < Operation *, int >CPofPredGraph;
map < Operation *, int >CPofPredGraph_;
map < Operation *, int >CPofPreRevGraph;
map < Operation *, int >CPofPreRevGraph_;
map < Operation *, map < Operation *, int > >CPofNodes;
map < int, map < Operation *, int > >ASAPofMultiThread;
map < int, map < Operation *, int > >ALAPofMultiThread;
map < Operation *, int > ASAPUC;
map < Operation *, int > ALAPUC;
map < Operation *, set < Operation * > >immediatePrecedentOperations;
map < Operation *, set < Operation * > >successorOperations;
map < int, set < int > >level_l_h;
map <int, map<Operation *, bool> > precedenceRecord;
map<int, int> levelbound_info;
map<int, int> endofLevel; // end of cut now
// container for source operations
// not used
set < Operation * >sourceOperations;
multiset < Operation  > topoSet;
// container for sink operations
// not used
set < Operation* > sinkOperations;
multiset < Operation > sortedSetByALAP;
multiset < Operation > sortedSetByCP;
bool config_echo = false;
bool config_level = false;
bool config_low = false;
int maxOpTraversed = 0;
int globalLow = 0;
int new_low = 0;
bool terminateBB = false;
bool basicfound = false;
bool completeBranchBound = false;
int total_traverse = 0;
int total_duration = 0;
int core_limit = 16;
int environment_core_limit = 96;
int core_number = 0;
//HANDLE semephore;
int assignment = 0;
int count = 0;
map < int, pthread_t > threadMap;
int latex_global;
int latex_optimal;
float latex_not_c;
float latex_not_t;
float latex_level_c;
float latex_level_t;
float latex_termi_c;
float latex_termi_t;
float latex_shrin_c;
float latex_shrin_t;
float latex_1p_c;
float latex_1p_t;
float latex_2p_c;
float latex_2p_t;
float latex_to_c;
float latex_to_t;
struct thread_ag
{
  int lower;
  int upper;
  int coreID;
  sem_t* assignmentSemaphore;//
  set < int > * assignmentMap;
};
struct search_ag
{
  int step;
  int op;
  int core;
  bool updateALAP;
  bool cpbound;
  bool levelbound;
  bool lowbound;
  bool preSearch;
  int * assignmentSemaphore; //
  set < int > * assignmentMap;
  search_strategy ss;
};
struct parallel_ag
{
  int assignmentSemaphore;//
  set<int> assignmentMap;
  int core_limit;
};
// variables for parallel algorithm
// need initializtion
map < int, map < Operation *, int > >currentSchedule_p;
map < int, map < Operation *, int > >optimalSchedule_p;
map < int, map < type, map < int, int > > > resources_p;
map < int, map < type, map < int, int > > > resource_snapshot_p;
int graph_count = 0;
// variables for parallel algorithm
fstream fout;
inline unsigned long long
GetCycleCount()
{
  //__asm _emit 0x0F
  //__asm _emit 0x31
  return 0;
}
void
floydWarshall()
{
  // init
  CPofNodes.clear();

  for(set < Dependency * >::const_iterator it =
        dependencies.begin(); it != dependencies.end(); it++)
    {
      CPofNodes[(*it)->source][(*it)->sink] = (*it)->source->delay;
    }

  for(int k = 1; k <= operations.size(); k++)
    {
      for(int i = 1; i <= operations.size(); i++)
        {
          for(int j = 1; j <= operations.size(); j++)
            {
              // int test1 =
              // CPofNodes[operations[i]][operations[j]];
              // int test2 =
              // CPofNodes[operations[i]][operations[k]];
              // int test3 =
              // CPofNodes[operations[k]][operations[j]];
              if(CPofNodes[operations[i]][operations[k]] != 0
                  && CPofNodes[operations[k]][operations[j]] != 0)
                CPofNodes[operations[i]][operations[j]] =
                  max(CPofNodes[operations[i]][operations[j]],
                      CPofNodes[operations[i]][operations[k]] +
                      CPofNodes[operations[k]][operations[j]]);
            }
        }
    }
}
// for procedure "getSubGraph" find the sink ops of a specified op
void
addSink(Operation * op, Graph * graph)
{
  if(op->adj.size() == 0)
    return;

  for(set < Dependency * >::const_iterator it = op->adj.begin();
      it != op->adj.end(); it++)
    {
      Dependency * dep = (*it);
      graph->dependencies.insert(dep);
      graph->operations.insert(dep->sink);
      addSink(dep->sink, graph);
    }
}
// for procedure "getPrecedenceGraph" find the source op of a
// specified op
void
addSource(Operation * op, Graph * graph, Graph * base)
{
  for(set < Dependency * >::const_iterator it =
        base->dependencies.begin(); it != base->dependencies.end();
      it++)
    {
      Dependency * dep = (*it);

      if(dep->sink == op)
        {
          graph->dependencies.insert(dep);
          graph->operations.insert(dep->source);
          addSource(dep->source, graph, base);
        }
    }
}
// for procedure "getPrecedenceGraph" find the source op of a
// specified op
void
addSource(Operation * op, Graph * graph)
{
  for(set < Dependency * >::const_iterator it = dependencies.begin();
      it != dependencies.end(); it++)
    {
      Dependency * dep = (*it);

      if(dep->sink == op)
        {
          graph->dependencies.insert(dep);
          graph->operations.insert(dep->source);
          addSource(dep->source, graph);
        }
    }
}
// get sub graph
Graph * getSubGraph(Operation * op)
{
  Graph * rs = new Graph();
  // const Operation *curOp = op;
  rs->operations.insert(op);
  // get source recursively
  addSink(op, rs);
  rs->initGraph();
  return rs;
}
// get precedence graph
Graph * getPrecedenceGraph(Operation * op, Graph * base)
{
  Graph * rs = new Graph();
  // const Operation *curOp = op;
  rs->operations.insert(op);
  // get source recursively
  addSource(op, rs, base);
  rs->initGraph();
  return rs;
}
// get precedence graph
Graph * getPrecedenceGraph(Operation * op)
{
  Graph * rs = new Graph();
  // const Operation *curOp = op;
  rs->operations.insert(op);
  // get source recursively
  addSource(op, rs);
  rs->initGraph();
  return rs;
}
// get reversed graph
Graph * getReversedGraph(Graph * graph)
{
  Graph * rs = new Graph();
  rs->operations = graph->operations;

  for(set < Dependency * >::const_iterator it =
        graph->dependencies.begin(); it != graph->dependencies.end();
      it++)
    {
      Dependency * dep1 = (*it);
      Dependency * dep2 = new Dependency(dep1->sink, dep1->source);
      rs->dependencies.insert(dep2);
    }

  rs->initGraph();
  return rs;
}
int
getCriticalPathLength(Operation * op, Graph * g, enum cptype type)
{
  if(type == cpofsub)
    {
      /*   set < int >rs;
       for( set < Operation * >::const_iterator it =
       g->sourceOps.begin(); it != g->sourceOps.end(); it++ )
       {
       int depth = 0;
       Operation * op = ( *it );
       rs.insert( DFS( g, &rs, op, depth, type, false ) );
       }
       int len = *rs.rbegin();
       return len; */
      int rs = 0;

      for(set<Operation*>::iterator it = g->sinkOp.begin(); it != g->sinkOp.end(); it++)
        {
          rs = max(rs, CPofNodes[op][*it]);
        }

      return rs;
    }
  else if(type == cpofsub_)
    {
      set < int >rs;

      for(set < Operation * >::const_iterator it =
            g->sourceOps.begin(); it != g->sourceOps.end(); it++)
        {
          int depth = 0;
          Operation * op = (*it);
          rs.insert(DFS(g, &rs, op, depth, type, true));
        }

      int len = *rs.rbegin();
      return len;
    }
  else if(type == cpofpred)
    {
      /*    if( g->operations.size() == 1 )
       {
       Operation * op = *g->operations.begin();
       return 0;
       }
       else
       {
       int rs = 0;
       Operation * sink = operations[( *g->sinkOp.begin() )->id];
       for( set<Operation*>::const_iterator it = g->sourceOps.begin(); it != g->sourceOps.end(); it++ )
       rs = max( rs, CPofNodes[operations[( *it )->id]][operations[( *g->sinkOp.begin() )->id]] );
       return rs;
       }
       */

      int rs = 0;

      for(set<Operation*>::iterator it = g->sourceOps.begin(); it != g->sourceOps.end(); it++)
        {
          rs = max(rs, CPofNodes[*it][op]);
        }

      return rs;
    }
  else if(type == cpofpred_)
    {
      if(g->operations.size() == 1)
        {
          //Operation * op = *g->operations.begin();
          return 1;
        }
      else
        {
          Operation * source = *g->sourceOps.begin();
          Operation * sink = *g->sinkOp.begin();
          return source->CPSubGraph - sink->CPSubGraph;
        }
    }
  else if(type == cpofpredresv)
    {
      if(g->operations.size() == 1)
        {
          Operation * op = *g->operations.begin();
          return op->delay;
        }
      else
        {
          Operation * source = *g->sourceOps.begin();
          Operation * sink = *g->sinkOp.begin();
          return sink->CPSubGraph - source->CPSubGraph + source->delay;
        }
    }

  return -1;
}
unsigned long long
getEstimatedSpace()
{
  unsigned long long rs = 1;

  for(int i = 1; i <= operations.size(); i++)
    rs *= (operations[i]->ALAP - operations[i]->ASAP);

  return rs;
}
// DFS for CP calculation
int
DFS(Graph * g, set < int >*rs, Operation * op, int depth,
    enum cptype type, bool isSimple)
{
  // printf( "DFS: processing op %d...\n", op->id );
  int *targetcp;

  switch(type)
    {
    case cpofsub:
      targetcp = &op->CPSubGraph;
      break;
    case cpofpred:
      targetcp = &op->CPPredGraph;
      break;
    case cpofpredresv:
      targetcp = &op->CPofPreRevGraph;
      break;
    }

  if(*targetcp != -1 && type == cpofsub)
    return *targetcp;

  bool hit = false;

  for(set < Dependency * >::const_iterator it =
        g->dependencies.begin(); it != g->dependencies.end(); it++)
    {
      Dependency * dep = (*it);

      if(dep->source == op)
        {
          *targetcp =
            max(op->delay + DFS(g, rs, dep->sink, depth, type, isSimple),
                *targetcp);
          hit = true;
        }
    }

  if(!hit)
    {
      *targetcp = isSimple ? 1 : op->delay;
    }

  return *targetcp;
}
// DFS for level calculation
void
DFS(Operation * op, int depth)
{
  // printf( "DFS Level: processing op %d...\n", op->id );
  if(op->visited)
    return;

  depth++;
  op->level = depth;
  level_l_h[depth].insert(op->id);

  if(op->adj.size() == 0)
    return;

  for(set < Dependency * >::const_iterator it = op->adj.begin();
      it != op->adj.end(); it++)
    {
      Dependency * dep = (*it);
      // calculate level on the fly
      DFS(dep->sink, depth);
    }

  op->visited = true;
}
void topoSort()
{
  set< int > tempOp;
  level_l_h.clear();
  level_count = 0;

  for(map<int, Operation *>::const_iterator it = operations.begin(); it != operations.end(); it++)
    {
      tempOp.insert((*it).second->id);
    }

  int levelCount = 1;

  while(tempOp.size() != 0)
    {
      set< int > tempOpSet;

      for(set < int >::const_iterator it =
            tempOp.begin(); it != tempOp.end(); it++)
        {
          Operation * op = operations[ *it ];
          bool noIn = true;

          for(set < Dependency* >::const_iterator it2 = op->in.begin(); it2 != op->in.end(); it2++)
            {
              Dependency * dep = *(it2);

              if(tempOp.find(dep->source->id) != tempOp.end())
                noIn = false;
            }

          if(noIn)
            tempOpSet.insert(*it);
        }

      for(set<int>::const_iterator it = tempOpSet.begin(); it != tempOpSet.end(); it++)
        {
          operations[*it]->level = levelCount;
          operations[*it]->sort_id = -levelCount;
          tempOp.erase(*it);
        }

      levelCount++;
      level_count = max(level_count, levelCount);
    }

  ///////////added by mingsong
  //  for(int l=1; l<=levelCount; l++)
  //  {
  //   history_level_info[l] = new vector<int>();
  //}
  for(set < Dependency * >::const_iterator edge_it = dependencies.begin(); edge_it != dependencies.end(); edge_it++)
    {
      int src = (*edge_it)->source->id;
      int dest = (*edge_it)->sink->id;
      int src_level = operations[src]->level;
      int dest_level = operations[dest]->level;

      for(int l = src_level; l < dest_level; l++)
        level_l_h[l].insert(src);
    }

  ///////////////////////
  level_count--;

  for(map<int, Operation*>::const_iterator it = operations.begin(); it != operations.end(); it++)
    {
      topoSet.insert(*(*it).second);
    }
}
void
initASAP()
{
  for(map < int, Operation * >::const_iterator it =
        operations.begin(); it != operations.end(); it++)
    {
      Operation * op = (*it).second;
      op->ASAP = CPofPredGraph[op] + 1;
    }
}
void
initALAP()
{
  for(map < int, Operation * >::const_iterator it =
        operations.begin(); it != operations.end(); it++)
    {
      Operation * op = (*it).second;
      //  printf("op%d cp sub pre prerev %d %d %d\n", op->id, CPofSubGraph[op], CPofPredGraph[op], CPofPreRevGraph[op]);
      op->ALAP = w - CPofSubGraph[op];
    }
}
void
printCurrentSchedule(int i)
{
  // fout << "current schedule:
  for(int j = 1; j <= i; j++)
    {
      printf("%d %%%.0f ", currentSchedule[operations[j]],
             (currentSchedule[operations[j]] - operations[j]->ASAP +
              1.0) / (operations[j]->ALAP - operations[j]->ASAP +
                      1.0) * 100);
      // fout << currentSchedule[operations[j]];
    }

  // fout <<"\n";
  printf("\n");
}
void
printCurrentSchedule(int core, int i)
{
  // fout << "current schedule:
  printf("thread %d: ", core);

  for(int j = 1; j <= i; j++)
    {
      printf("%d ", currentSchedule_p[core][operations[j]->sortedOp]);
      //( currentSchedule_p[core][operations[j]] -
      // operations[j]->ASAP + 1.0 ) / ( operations[j]->ALAP -
      //                                operations[j]->ASAP +
      //                                1.0 ) * 100 );
      // fout << currentSchedule[operations[j]];
    }

  // fout <<"\n";
  printf("\n");
}
void
writeSchedule(char *info)
{
  fout << info << "writesche(): found a schedule:\n";

  for(int j = 1; j <= operations.size(); j++)
    {
      fout << currentSchedule[operations[j]] << "\t" <<
           operations[j]->ASAP << "\t" << operations[j]->ALAP << "\n";
    }

  fout << "\n";
  fout.flush();
}
void
writeSchedule(int core)
{
  fout << "found a schedule at thread " << core << " ";

  for(int j = 1; j <= operations.size(); j++)
    {
      fout << currentSchedule_p[core][operations[j]] << " ";
    }

  fout << "\n";
  fout.flush();
}
void
saveASAP()
{
  for(int i = 1; i <= operations.size(); i++)
    {
      // tempASAP[operations[i]] = operations[i]->ASAP;
    }
}
void
restoreASAP()
{
  for(int i = 1; i <= operations.size(); i++)
    {
      // operations[i]->ASAP = tempASAP[operations[i]];
    }
}
bool CPBound(Operation * op)
{
  bool rs = true;
  FuncTimer::checkin(cpbound_t);
  int l = *level_l_h[op->level].begin();
  int h = *level_l_h[op->level].rbegin();

  for(int i = l; i <= h; i++)
    {
      Operation * opi = operations[i];
      rs =
        rs & (currentSchedule[op] + CPofSubGraph[op] >=
              optimalSchedule[opi] + CPofSubGraph[opi]);
    }

  FuncTimer::checkout(cpbound_t);
  return rs;
}
bool CPBound(int core, Operation * op)
{
  bool rs = true;
  int l = *level_l_h[op->level].begin();
  int h = *level_l_h[op->level].rbegin();

  for(int i = l; i <= h; i++)
    {
      Operation * opi = operations[i];
      rs =
        rs & (currentSchedule_p[core][op] + CPofSubGraph[op] >=
              optimalSchedule_p[core][opi] + CPofSubGraph[opi]);
    }

  return rs;
}
void
branchBoundRCS_h(int i)
{
  if(i == operations.size() + 1)
    {
      if(optimalScheduleTime > calculateMaxScheduleTime())
        {
          optimalSchedule = currentSchedule;
          optimalScheduleTime = calculateMaxScheduleTime();
        }
    }
  else
    {
      Operation * op = operations[i];

      for(int step = op->ASAP; step <= op->ALAP; step++)
        {
          map < Operation *, int >tempASAP;

          // save ASAP
          for(int i = 1; i <= operations.size(); i++)
            tempASAP[operations[i]] = operations[i]->ASAP;

          if(isResourceAvailable(step, op->t, op->delay))
            {
              int l = lowBound(op);
              int u = upperBound(op);

              if(u < optimalScheduleTime)
                {
                }
            }
        }
    }
}
// main HLS algorithm +
void
branchBoundRCS(int i, bool update, bool bCPbound, bool blevelBound)
{
  total_traverse++;
  maxOpTraversed = max(maxOpTraversed, i);

  // printf( "branchBoundRCS: processing op %d...\n", i );
  if(i <= operations.size())
    {
      Operation * op = operations[i];

      for(int step = op->ASAP; step <= op->ALAP; step++)
        {
          map < Operation *, int >tempASAP;

          // save ASAP
          for(int i = 1; i <= operations.size(); i++)
            tempASAP[operations[i]] = operations[i]->ASAP;

          // pass step as step into isPrecedence &
          // isResourceAvailable
          if( // isPrecedence( op, step ) &&
            isResourceAvailable(step, op->t, op->delay))
            {
              currentSchedule[op] = step;

              if(i <= 4)
                printCurrentSchedule(i);

              // //todo: justify
              if(bCPbound && CPBound(op))
                return;

              if(blevelBound && levelBound(op))
                return;

              // if( bTOPObound && topoBound( op ) )
              // continue;
              if( // !blowbound ||
                lowBound(op) < optimalScheduleTime)
                {
                  occupyResource(step, op->t, op->delay);
                  updateASAP(op, step);

                  if(update)
                    {
                      updateALAP(op);
                    }

                  branchBoundRCS(i + 1, update, bCPbound,
                                 blevelBound);
                  releaseResource(step, op->t, op->delay);
                }
              else
                {
                  // printf( "*" );
                  // fout << "omit from lowbound at op " << op->id
                  // << " at level " << op->level << "\n";
                  // printf( "return from low bound at " );
                  // printCurrentSchedule( i );
                  continue;
                }
            }

          for(int i = 1; i <= operations.size(); i++)
            operations[i]->ASAP = tempASAP[operations[i]];
        }
    }
  else
    {
      completeBranchBound = true;
      int scheduleTime = calculateMaxScheduleTime();
      printf("bb: found a schedule: %d ", scheduleTime);
      lastFeasibleSchedule = currentSchedule;

      for(int i = 1; i <= operations.size(); i++)
        printf("%d", currentSchedule[operations[i]]);

      printf("\n");
      fout << "bb: found a shcedule\n";
      writeSchedule("Found by BB");
      fout.flush();

      if(optimalScheduleTime >= scheduleTime)
        {
          completeBranchBound = true;
          optimalScheduleTime = scheduleTime;
          optimalSchedule = currentSchedule;
          // update alap
          // printf( "found update!\n" );
          // for( int k = 1; k <= operations.size(); k++ )
          // {
          // Operation * opk = operations[k];
          // opk->ALAP = min( opk->ALAP, optimalScheduleTime -
          // CPofPreRevGraph[opk] + 1 );
          // }
        }
    }
}
void
coreScheduler(void *arg)
{
  thread_ag * ta = (thread_ag *) arg;
  int current = ta->lower;
  pthread_t coreThread;//

  while(current <= ta->upper)
    {
      search_ag * sa = (search_ag *) malloc(sizeof(search_ag));
      sa->core = ta->coreID;
      sa->op = 1;
      sa->step = current;

      sa->updateALAP = true;
      sa->preSearch = false;
      sa->lowbound = true;
      sa->levelbound = false;

      // WaitForSingleObject( *ta->assignmentSemaphore, 0L );
      sem_wait(ta->assignmentSemaphore);

      if(ta->assignmentMap->find(current) == ta->assignmentMap->end())
        {
          current++;
          free(sa);
          //  ReleaseSemaphore( *ta->assignmentSemaphore, 1, NULL );
          sem_post(ta->assignmentSemaphore);
          //sem_post( ta->assignmentSemaphore );
          continue;
        }

      ta->assignmentMap->erase(current);
      //ReleaseSemaphore( *ta->assignmentSemaphore, 1, NULL );
      sem_post(ta->assignmentSemaphore);
      //coreThread = ( int )_beginthread( branchBoundRCS_thread, 0, ( void* )sa );//
      printf("core_scheduler: start task at %d on core %d\n", sa->step, ta->coreID);
      pthread_create(&coreThread, NULL, (void * (*)(void*))branchBoundRCS_thread, (void*)sa);

      //SetThreadAffinityMask (coreThread, (DWORD_PTR) ta->coreID);
      // SetThreadPriority( coreThread, THREAD_PRIORITY_HIGHEST );
      //WaitForSingleObject( coreThread, INFINITE );
      pthread_join(coreThread, NULL);
      printf("core_scheduler: finished task at %d on core %d\n", sa->step, ta->coreID);

      free(sa);
      current++;
    }

  //WaitForSingleObject( *ta->assignmentSemaphore, 0L );
  sem_wait(ta->assignmentSemaphore);
  int remain = ta->assignmentMap->size();

  while(remain != 0)
    {
      search_ag * sa = (search_ag *) malloc(sizeof(search_ag));
      sa->core = ta->coreID;
      sa->op = 1;
      sa->step = *ta->assignmentMap->begin();

      sa->updateALAP = true;
      sa->preSearch = false;
      sa->lowbound = true;
      sa->levelbound = false;

      ta->assignmentMap->erase(sa->step);
      //ReleaseSemaphore( *ta->assignmentSemaphore, 1, NULL );
      sem_post(ta->assignmentSemaphore);
      // coreThread = ( int )_beginthread( branchBoundRCS_thread, 0, ( void* )sa );//
      //     pthread_attr_setschedparam(<#pthread_attr_t *#>, <#const struct sched_param *#>)
      //SetThreadAffinityMask (coreThread, (DWORD_PTR) ta->coreID);
      pthread_attr_t attr;
      sched_param param;
      int newprio = 99;
      pthread_attr_init(&attr);
      pthread_attr_getschedparam(&attr, &param);
      param.sched_priority = newprio;
      pthread_attr_setschedparam(&attr, &param);
      printf("core_scheduler: start task at %d on core %d\n", sa->step, ta->coreID);

      pthread_create(&coreThread, &attr, (void * (*)(void*))branchBoundRCS_thread, (void*) sa);

      //     pthread_setaffinity_np();
      // SetThreadPriority( coreThread, THREAD_PRIORITY_HIGHEST );
      //WaitForSingleObject( coreThread, INFINITE );

      pthread_join(coreThread, NULL);
      printf("core_scheduler: finished task at %d on core %d\n", sa->step, ta->coreID);

      free(sa);
      //WaitForSingleObject( *ta->assignmentSemaphore, 0L );
      sem_wait(ta->assignmentSemaphore);
      remain = ta->assignmentMap->size();
    }

  //ReleaseSemaphore( *ta->assignmentSemaphore, 1, NULL );
  sem_post(ta->assignmentSemaphore);
}
void
printInfo(char *str)
{
  printf(str);
  printf("\n");
  fout << str << "\n";
  //fout.flush();
}
void
testDriver(char *info, bool shrink, bool lowbound, bool level, bool twophase)
{
  fout << "\nshrink: " << shrink << " termination: " << lowbound << " level: " << level << " two-phase: " << twophase << "\n";
  resetContext();
  printInfo("\n");
  printInfo(info);
  search_ag * sa = (search_ag *) malloc(sizeof(search_ag));
  sa->core = 1;
  sa->op = 1;
  sa->step = -1;
  sa->updateALAP = shrink;
  sa->preSearch = twophase;
  sa->levelbound = level;
  sa->lowbound = lowbound;
  printInfo("pre-search...\n");
  updateALAP(1, NULL, shrink);
  double start = 0;
  double end = 0;

  if(twophase)
    {
      start = GetTickCount();
      currentSchedule_p[1].clear();
      branchBoundRCS_thread(sa);
      end = GetTickCount();
      fout << "pre-search total duration: " << end - start << "\n";
      latex_1p_c = total_traverse;
      latex_1p_t = end - start;
    }

  fout << "pre traverse: " << total_traverse << "\n";
  total_traverse = 0;
  sa->preSearch = false;
  printInfo("formal-search...\n");
  start = GetTickCount();
  currentSchedule_p[1].clear();
  branchBoundRCS_thread(sa);
  end = GetTickCount();
  printInfo(info);
  latex_optimal = optimalScheduleTime;
  fout << "The optimal schedule time is " << optimalScheduleTime <<
       "\n";

  for(int i = 1; i <= operations.size(); i++)
    {
      Operation * op = operations[i];
      fout << op->id << "\t" << optimalSchedule_p[1][op] << "\n";
    }

  fout << "Finished branchbound? " << completeBranchBound << "\n";
  total_duration = end - start;
  fout << "total duration: " << end - start << "\n";
  fout << "total traverse: " << total_traverse << "\n";
  fout << "max op traversed: " << maxOpTraversed << "\n";

  for(int i = 1; i <= FuncTimer::tickets.size(); i++)
    {
      fout << i << " " << FuncTimer::tickets[(func_type) i] << " " <<
           FuncTimer::times[(func_type) i] << "\n";
    }

  fout.flush();
}
// main HLS algorithm +
void
branchBoundRCS_thread(void *arg)
{
  search_ag * sa = (search_ag *) arg;
  int i = sa->op;
  int core = sa->core;

  if(i == 1 && sa->preSearch)
    {
      printf("init low: %d\n", globalLow);
    }

  maxOpTraversed = max(maxOpTraversed, i);

  if(i <= operations.size())
    {
      Operation * op = operations[i]->sortedOp;
      int start_step;
      int end_step;

      if(sa->step == -1)
        {
          //start_step = min(ASAPofMultiThread[core][op], ASAPUC[op]);
          start_step = ASAPofMultiThread[core][op];
          end_step = ALAPofMultiThread[core][op];
        }
      else
        {
          start_step = sa->step;
          end_step = sa->step;
        }

      for(int step = start_step; step <= end_step; step++)
        {
          if(sa->lowbound && optimalScheduleTime == globalLow)
            {
              printInfo("lower bound == upper bound, terminate\n");
              return;
            }
          else if(optimalScheduleTime < globalLow)
            {
              printInfo("upper < low error!\n");
              return;
            }

          total_traverse++;

          if(sa->lowbound && optimalScheduleTime <= globalLow)
            {
              return;
            }

          int low = 0;
          map < Operation *, int >tempASAP;

          // save ASAP
          for(int i = 1; i <= operations.size(); i++)
            tempASAP[operations[i]] = ASAPofMultiThread[core][operations[i]];

          // pass step as step into isPrecedence &
          // isResourceAvailable
          if(// isPrecedence( core, op, step ) &&
            isResourceAvailable(core, step, op->t, op->delay))
            {

              //            if( i <= 2 )
              //if( config_echo )
              //if (i <= 4)
              //   printCurrentSchedule (core, i);
              // todo: justify/
              //        if( sa->cpbound && CPBound( core, op ) )
              {
                // printf("CP hint\n");
                //        return;
              }
              //               if( ( !sa->preSearch && sa->levelbound  && levelBound( core, op, step ) ) )
              {
                // printf( "return from level bound at " );
                // printCurrentSchedule( i );
                // printf( "terminatebb at op %d at level %d\n",
                // i, op->level );
                // terminateBB = true;
                //                  if( config_echo )
                //                       fout << "return from levelbound at op " <<
                //                           op->id << " at level " << op->level << "\n";
                // printf("LEVEL hint\n");
                //                   return;
                //
              }


              low = lowBound(core, operations[sa->op]);
              updateALAP(core, operations[sa->op], sa->updateALAP);

              low = 0;

              if(low < optimalScheduleTime)
                {
                  //printf("currentSchedule_p[%d][%d] = %d\n", sa->core, op->id, step);
                  currentSchedule_p[sa->core][op] = step;
                  // printCurrentSchedule( sa->core, i );


                  occupyResource(core, step, op->t, op->delay);


                  updateASAP(core, op, step);

                  search_ag * sa2 =
                    (search_ag *) malloc(sizeof(search_ag));
                  sa2->op = i + 1;
                  sa2->step = -1;
                  sa2->core = core;
                  sa2->updateALAP = sa->updateALAP;
                  sa2->cpbound = sa->cpbound;
                  sa2->preSearch = sa->preSearch;
                  sa2->lowbound = sa->lowbound;
                  sa2->levelbound = sa->levelbound;
                  sa2->updateALAP = sa->updateALAP;

                  if((op->id != endofLevel[op->level] && sa->preSearch) || !sa->preSearch)
                    {

                      branchBoundRCS_thread((void *)(sa2));
                    }

                  free(sa2);
                  releaseResource(core, step, op->t, op->delay);
                }
              else
                {
                  if(config_echo)
                    fout << "omit from lowbound at op " << op->id
                         << " at level " << op->level << "\n";

                  continue;
                }
            }

          // restore ASAP
          for(int i = 1; i <= operations.size(); i++)
            ASAPofMultiThread[core][operations[i]] =
              tempASAP[operations[i]];
        }
    }
  else
    {
      completeBranchBound = true;
      int scheduleTime = calculateMaxScheduleTime(core);
      char str[256];
      //       sprintf( str, "bb: else: found a schedule: %d\n", scheduleTime );
      //       printInfo( str );
      lastFeasibleSchedule = currentSchedule_p[core];

      //       for( int i = 1; i <= operations.size(); i++ )
      //           printf( "%d", currentSchedule_p[core][operations[i]] );
      //       writeSchedule( core );
      //       fout.flush();
      if(optimalScheduleTime >= scheduleTime)
        {
          completeBranchBound = true;
          optimalScheduleTime = scheduleTime;
          optimalSchedule_p[core] = currentSchedule_p[core];
          resource_snapshot_p[core] = resources_p[core];
          //added by mingsong
          //   for(int i=1; i<=level_count; i++)
          {
            vector<int> * newS = new vector<int>();
            newS->push_back(0);
            history_level_info.push_back(newS);

            for(int i = 1; i <= operations.size(); i++)
              newS->push_back(currentSchedule_p[core][operations[i]]);

            //	for(  set < int >::const_iterator set_it = level_l_h[i].begin(); set_it != level_l_h[i].end(); set_it++   )
            //	history_level_info[i]->back()->push_back(currentSchedule[operations[*set_it]] );

          }
        }
    }
}
// main HLS algorithm +
void
basicEnu(int i)
{
  if(basicfound)
    return;

  if(i <= operations.size())
    {
      Operation * op = operations[i];
      int step = op->ASAP;

      // for( int step = op->ASAP; step <= op->ALAP; step++ )
      while(true)
        {
          // pass step as step into isPrecedence &
          // isResourceAvailable
          if(isPrecedence(op, step)
              && isResourceAvailable(step, op->t, op->delay))
            {
              if(basicfound)
                return;

              currentSchedule[op] = basicSchedule[op] = step;
              occupyResource(step, op->t, op->delay);
              basicEnu(i + 1);
              releaseResource(step, op->t, op->delay);
            }

          step++;
        }
    }
  else
    {
      printf("basicEnu: found a schedule... %d\n",
             calculateMaxScheduleTime());
      completeBranchBound = true;
      int scheduleTime = calculateMaxScheduleTime();

      if(scheduleTime <= basicSchedulingTime)
        {
          basicSchedulingTime = scheduleTime;
          fout << "initial basic schedule: " << scheduleTime << "\n";
          writeSchedule("Found by Basic");
        }

      optimalScheduleTime = w = min(w, basicSchedulingTime);
      basicfound = true;
      return;
    }
}
// evaluate all schedules and pick the max value +
int
calculateMaxScheduleTime()
{
  int current_schedule_time = 0;
  int temp = 0;

  for(int i = 1; i <= operations.size(); i++)
    {
      temp = currentSchedule[operations[i]] + operations[i]->delay - 1;
      current_schedule_time = max(current_schedule_time, temp);
    }

  return current_schedule_time;
}
int
calculateMaxScheduleTime(int core)
{
  int current_schedule_time = 0;
  int temp = 0;

  for(int i = 1; i <= operations.size(); i++)
    {
      temp =
        currentSchedule_p[core][operations[i]] + operations[i]->delay - 1;
      current_schedule_time = max(current_schedule_time, temp);
    }

  return current_schedule_time;
}
// occupy resource of specified type
void
occupyResource(int step, type t, int delay)
{
  FuncTimer::checkin(occupyResource_t);

  for(int i = step; i < step + delay; i++)
    {
      // occupy the resource for subsequent steps
      resources[t][i]++;
    }

  FuncTimer::checkout(occupyResource_t);
}
void
occupyResource(int core, int step, type t, int delay)
{
  FuncTimer::checkin(occupyResource_t);

  for(int i = step; i < step + delay; i++)
    {
      // occupy the resource for subsequent steps
      resources_p[core][t][i]++;
    }

  FuncTimer::checkout(occupyResource_t);
}
// release resource of specified type
void
releaseResource(int step, type t, int delay)
{
  FuncTimer::checkin(releaseResource_t);

  for(int i = step; i < step + delay; i++)
    {
      // release the resource for subsequent steps
      resources[t][i]--;
    }

  FuncTimer::checkout(releaseResource_t);
}
void
releaseResource(int core, int step, type t, int delay)
{
  FuncTimer::checkin(releaseResource_t);

  for(int i = step; i < step + delay; i++)
    {
      // release the resource for subsequent steps
      resources_p[core][t][i]--;
    }

  FuncTimer::checkout(releaseResource_t);
}
void
updateASAP(Operation * op, int step)
{
  FuncTimer::checkin(updateasap_t);

  for(set < Operation * >::const_iterator it =
        successorOperations[op].begin();
      it != successorOperations[op].end(); it++)
    {
      if((*it)->ASAP < step + CPofNodes[op][(*it)])
        {
          // printf( "updateASAP: updated op%d from %d to %d!\n", (
          // *it )->id, ( *it )->ASAP, step + CPofNodes[op][( *it )]
          // );
          // fout << "updateASAP: updated op" << ( *it )->id << "
          // from " << ( *it )->ASAP << "to " << step +
          // CPofNodes[op][( *it )] << "!\n";
          (*it)->ASAP = max((*it)->ASAP, step + CPofNodes[op][(*it)]);	// todo:
          // cp
          // between
          // opi
          // and
          // opj
        }
    }

  FuncTimer::checkout(updateasap_t);
}
void
updateASAP(int core, Operation * op, int step)
{
  FuncTimer::checkin(updateasap_t);

  for(set < Operation * >::const_iterator it =
        successorOperations[op].begin();
      it != successorOperations[op].end(); it++)
    {
      if(ASAPofMultiThread[core][(*it)] <
          step + CPofNodes[op][(*it)])
        {
          // printf( "updateASAP: updated op%d from %d to %d!\n", (
          // *it )->id, ( *it )->ASAP, step + CPofNodes[op][( *it )]
          // );
          // fout << "updateASAP: updated op" << ( *it )->id << "
          // from " << ( *it )->ASAP << "to " << step +
          // CPofNodes[op][( *it )] << "!\n";
          ASAPofMultiThread[core][(*it)] = max(ASAPofMultiThread[core][(*it)], step + CPofNodes[op][(*it)]);	// todo:
          // ASAPofMultiThread[core][( *it )] = min( ASAPofMultiThread[core][( *it )], ASAPUC[op]);
          // cp
          // between
          // opi
          // and
          // opj
        }
    }

  FuncTimer::checkout(updateasap_t);
}
void
updateALAP(Operation * op)
{
  // if( op->id == 27 )
  // int test = 0;
  if(op->id == operations.size())
    return;

  FuncTimer::checkin(updateALAP_t);
  map < type, map < int, int > >resources_ = resources;
  map < Operation *, int >tempSchedule = currentSchedule;
  multiset < Operation > L_;
  map < int, int >L_array;
  map < int, int >S_;
  int w_ = 0;

  for(int i = 1; i <= op->id; i++)
    {
      S_[i] = currentSchedule[operations[i]];
    }

  for(int i = op->id + 1; i <= operations.size(); i++)
    {
      operations[i]->sort_id = -operations[i]->ALAP;
      L_.insert(*operations[i]);
    }

  int count = 1;

  for(multiset < Operation >::iterator it = L_.begin();
      it != L_.end(); it++)
    {
      L_array[count] = (*it).id;
      count++;
    }

  for(int k = 1; k <= operations.size() - op->id; k++)
    {
      Operation * opk = operations[L_array[k]];
      // todo: opi or opk?
      // note: opk is input for single
      int j = 1;

      while(true)
        {
          if(isPrecedence(opk, j)
              && isResourceAvailable(j, opk->t, opk->delay))
            {
              // only occupy, no release is needed
              occupyResource(j, opk->t, opk->delay);
              S_[opk->id] = j;
              currentSchedule[opk] = j;
              break;
            }

          j++;
        }
    }

  for(int l = 1; l <= operations.size() - op->id; l++)
    {
      Operation * op = operations[L_array[l]];

      if(S_[op->id] == 0)
        continue;

      w_ = max(S_[op->id] + op->delay, w_);
    }

  if(w_ == 0)
    return;

  // printf( "w_:w %d:%d!\n", w_, w );
  // todo: how to update w
  if(w_ < optimalScheduleTime)
    {
      printf("updateALAP: updated from %d to %d!\n",
             optimalScheduleTime, w_);
      fout << "updateALAP: updated from " << optimalScheduleTime <<
           " to " << w_ << "!\n";

      for(int k = 1; k <= operations.size(); k++)
        {
          Operation * opk = operations[k];
          opk->ALAP = w_ - CPofSubGraph[opk];
        }

      writeSchedule("Update by UpdateALAP");
      w = optimalScheduleTime = w_;
      optimalSchedule = currentSchedule;
    }

  // restore resource usage pool
  resources = resources_;
  currentSchedule = tempSchedule;
  FuncTimer::checkout(updateALAP_t);
}
void
updateALAP(int core, Operation * op, bool shrink)
{
  //  printf("op11 has step:%d\n", ASAPofMultiThread[core][operations[11]]);
  // if( op->id == 27 )
  // int test = 0;
  int endid = (op == NULL) ? 0 : op->id - 1;

  if(endid == operations.size())
    return;

  map < type, map < int, int > >resources_ = resources_p[core];
  map < Operation *, int >tempSchedule = currentSchedule_p[core];
  multiset < Operation > L_;
  map < int, int >L_array;
  map < int, int >S_;
  int w_ = 0;

  for(int i = 1; i <= endid; i++)
    S_[i] = currentSchedule_p[core][operations[i]->sortedOp];

  for(int i = endid + 1; i <= operations.size(); i++)
    {
      //     operations[i]->sortedOp->sort_id = -operations[i]->sortedOp->ALAP ;
      switch(global_listorder)
        {
        case byasap:
          operations[i]->sortedOp->sort_id = -operations[i]->sortedOp->ASAP;
          break;
        case byalap:
          operations[i]->sortedOp->sort_id = -operations[i]->sortedOp->ALAP;
          break;

        default:
          break;
        }

      L_.insert(*operations[i]->sortedOp);
    }

  int count = 1;

  for(multiset < Operation >::iterator it = L_.begin();
      it != L_.end(); it++)
    {
      L_array[count] = (*it).id;
      count++;
    }

  for(int k = 1; k <= operations.size() - endid; k++)
    {
      Operation * opk = operations[L_array[k]];
      // todo: opi or opk?
      // note: opk is input for single
      int j = ASAPofMultiThread[core][opk];

      while(true)
        {
          if(isPrecedence(core, opk, j)
              && isResourceAvailable(core, j, opk->t, opk->delay))
            {
              // only occupy, no release is needed
              occupyResource(core, j, opk->t, opk->delay);
              S_[opk->id] = j;
              currentSchedule_p[core][opk] = j;
              break;
            }

          j++;
        }
    }

  for(int l = 1; l <= operations.size(); l++)
    {
      Operation * op = operations[l];
      //       if( S_[op->id] == 0 )
      //           continue;
      w_ = max(currentSchedule_p[core][op] + op->delay - 1, w_);
    }

  if(w_ == 0)
    return;

  // printf( "w_:w %d:%d!\n", w_, w );
  // todo: how to update w
  if(w_ < optimalScheduleTime)
    {
      char str[256];
      sprintf(str, "updateALAP: upper bound updated from %d to %d at core %d at op %d!",
              optimalScheduleTime, w_, core, (op == NULL ? 0 : op->sortedOp->id));
      //    if( config_echo )
      printInfo(str);

      if(shrink)
        {
          for(int l = 1; l <= core_number; l++)
            {
              for(int k = 1; k <= operations.size(); k++)
                {
                  Operation * opk = operations[k];
                  ALAPofMultiThread[core_number][opk] = opk->ALAP = min(ALAPofMultiThread[core_number][opk], w_ - CPofSubGraph[opk]);
                  sprintf(str, "updateALAP: op %d update to %d at core %d at op %d!",
                          k, ALAPofMultiThread[core][opk], core, (op == NULL ? 0 : op->sortedOp->id));

                  if(config_echo)
                    printInfo(str);
                }
            }
        }

      w = optimalScheduleTime = min(optimalScheduleTime, w_);
      optimalSchedule_p[core] = currentSchedule_p[core];
      printf("op11 has step:%d\n", optimalSchedule_p[core][operations[11]]);
      resource_snapshot_p[core] = resources_p[core];
      //   for(int i=1; i<=level_count; i++)
      //	   {
      //		history_level_info[i]->push_back(new vector<int> ());
      //
      // 	for(  set < int >::const_iterator set_it = level_l_h[i].begin(); set_it != level_l_h[i].end(); set_it++   )
      //	history_level_info[i]->back()->push_back(currentSchedule_p[core][operations[*set_it]] );
      //
      //	   }
      {
        vector<int> * newS = new vector<int>();
        newS->push_back(0);
        history_level_info.push_back(newS);

        for(int i = 1; i <= operations.size(); i++)
          newS->push_back(currentSchedule_p[core][operations[i]]);

        //	for(  set < int >::const_iterator set_it = level_l_h[i].begin(); set_it != level_l_h[i].end(); set_it++   )
        //	history_level_info[i]->back()->push_back(currentSchedule[operations[*set_it]] );

      }
      /*
       for( int i = 1; i <= level_count; i++ )
       {
       map<int, int> maxLow;
       for( set < int >::const_iterator it = level_l_h[i].begin();
       it != level_l_h[i].end(); it++ )
       {
       maxLow[operations[*it]->graph] =
       max( maxLow[operations[*it]->graph],
       optimalSchedule_p[core][operations[*it]] +
       CPofSubGraph[operations[*it]] );
       }
       for( set < int >::const_iterator it =
       level_l_h[i].begin(); it != level_l_h[i].end();
       it++ )
       {
       operations[*it]->ALAP =
       min( operations[*it]->ALAP,
       maxLow[operations[*it]->graph] - CPofPreRevGraph[operations[*it]] + 1 );
       }
       }
       */
    }

  // restore resource usage pool
  resources_p[core] = resources_;
  currentSchedule_p[core] = tempSchedule;
  //	globalLow = max(globalLow, NULL);
}
//
bool levelBound(Operation * op)
{
  // if( op->id == 28 )
  // {
  // int test = 0;
  // }
  FuncTimer::checkin(levelbound_t);
  int l = *level_l_h[op->level].begin();
  int h = *level_l_h[op->level].rbegin();
  printf("level %d, %d \n", l , h);
  // getLhHh( &l, &h, op );
  bool temp_bool = true;

  if(op->id != h)
    {
      FuncTimer::checkout(levelbound_t);
      return false;
    }

  if(op->id == h)
    {
      //map < int, set < int > >level_l_h;
      //      for( int i = l; i <= h; i++ )
      for(set < int >::const_iterator set_it = level_l_h[op->level].begin(); set_it != level_l_h[op->level].end(); set_it++)
        temp_bool = temp_bool &
                    (currentSchedule[operations[*set_it]] >= optimalSchedule[operations[*set_it]]);	// ||

      if(temp_bool)
        {
          printf("hit level\n");
          return true;
        }

      for(int iteration = 0; iteration < history_level_info.size(); iteration++)
        {
          if(temp_bool)
            {
              printf("compare history %d \n", iteration + 1);
            }

          temp_bool = true;

          for(set < int >::const_iterator set_it = level_l_h[op->level].begin(); set_it != level_l_h[op->level].end(); set_it++)
            {
              temp_bool = temp_bool &
                          (currentSchedule[operations[*set_it]] >= history_level_info[iteration]->at(*set_it));
            }

          //	for( int i = l; i <= h; i++,ind++ )
          //		temp_bool = temp_bool &
          //			( currentSchedule[operations[i]] >= (history_level_info[op->level]->at(iteration))->at(ind));
          if(temp_bool)
            {
              return true;
            }
        }

      /*
       * for( int i = l; i <= op->id - 1; i++ )
       if( (
       * currentSchedule[op] > currentSchedule[operations[i]] &&
       * CPofSubGraph[op] > CPofSubGraph[operations[i]] && op->t ==
       * operations[i]->t ) ||
       ( currentSchedule[op] <
       * currentSchedule[operations[i]] && CPofSubGraph[op] <
       * CPofSubGraph[operations[i]] && op->t == operations[i]->t )
       * )
       {
       FuncTimer::checkout( levelbound_t );
       return true;
       * }
       */
      FuncTimer::checkout(levelbound_t);

      //   return temp_bool;
    }

  /*
   *
   for( int i = l; i <= op->id - 1; i++ )
   if( (
   * currentSchedule[op] > currentSchedule[operations[i]] &&
   * CPofSubGraph[op] > CPofSubGraph[operations[i]] && op->t ==
   * operations[i]->t ) ||
   ( currentSchedule[op] <
   * currentSchedule[operations[i]] && CPofSubGraph[op] <
   * CPofSubGraph[operations[i]] && op->t == operations[i]->t ) )
   * {
   FuncTimer::checkout( levelbound_t );
   return true;
   }
   //(
   * currentSchedule[op] + CPofSubGraph[op] >= optimalScheduleTime
   * );
   FuncTimer::checkout( levelbound_t );
   return false;
   * if( temp_bool )
   return true;
   else
   return false;
   */
  return false;
}
bool topoBound(Operation * op)
{
  int l = *level_l_h[op->level].begin();
  int h = *level_l_h[op->level].rbegin();

  for(int i = l; i <= op->id - 1; i++)
    if((currentSchedule[op] > currentSchedule[operations[i]]
        && CPofSubGraph[op] > CPofSubGraph[operations[i]]
        && op->t == operations[i]->t)
        ||
        (currentSchedule[op] < currentSchedule[operations[i]]
         && CPofSubGraph[op] < CPofSubGraph[operations[i]]
         && op->t == operations[i]->t))
      {
        return true;
      }

  return false;
}
bool levelBound(int core, Operation * op, int step)
{
  bool temp_bool = true;
  bool  a_res = true;
  bool m_res = true;

  if(op->id != endofLevel[op->level])
    return false;
  else
    {
      for(set<int>::const_iterator it = level_l_h[op->level].begin(); it != level_l_h[op->level].end(); it++)
        temp_bool = temp_bool &
                    (currentSchedule_p[core][operations[*it]] > optimalSchedule_p[core][operations[*it]]);

      // prune when all steps are larger
      // cannot prove the transitivity

      /* 	for( set<int>::const_iterator it = level_l_h[op->level].begin(); it!=level_l_h[op->level].end(); it++ )
       {
       a_res = a_res & ( resources_p[core][add][ currentSchedule_p[core][operations[*it]]  ]
       >= resource_snapshot_p[core][add][ optimalSchedule_p[core][operations[*it]]  ]);
       m_res = m_res & ( resources_p[core][multiplication][ currentSchedule_p[core][operations[*it]]  ]
       >= resource_snapshot_p[core][multiplication][ optimalSchedule_p[core][operations[*it]]  ]);
       }*/
      //	for ( int i=1; i<=step; i++ )
      //	{
      //		res_count += resources_p[core][add][i] - resource_snapshot_p[core][add][i];
      //		res_count += resources_p[core][multiplication][i] - resource_snapshot_p[core][multiplication][i];
      //	}

    }

  //  return temp_bool && (res_count>=0);
  //if(temp_bool && a_res && m_res) printf("level bound gets effect \n");
  // return temp_bool && a_res && m_res;
  if(temp_bool) printf("level bound gets effect \n");

  return temp_bool ;
}
// calculate Lh and Hh
void
getLhHh(int *l, int *h, Operation * op)
{
  int level = op->level;
  set < int >opWithSameLevel;

  for(map < int, Operation * >::const_iterator it =
        operations.begin(); it != operations.end(); it++)
    {
      Operation * op = (*it).second;

      if(op->level == level)
        opWithSameLevel.insert(op->id);
      else
        continue;
    }

  *l = *opWithSameLevel.begin();
  *h = *opWithSameLevel.rbegin();
}
int
upperBound(Operation * op)
{
  int rs = 0;
  // similar to updateALAP except for using ALAP as the priority
  return rs;
}
// get low bound
int
lowBound(Operation * op)
{
  map < type, map < int, int > >resources_ = resources;
  map < Operation *, int >tempSchedule = currentSchedule;
  // if( op->id == 28 )
  // int test = 0;
  FuncTimer::checkin(lowbound_t);
  int l = *level_l_h[op->level].begin();
  int h = *level_l_h[op->level].rbegin();
  int lowBoundTime = 0;
  int temp = 0;
  map < Operation *, int >start;

  // getLhHh( &l, &h, op );
  for(int k = l; k <= op->id; k++)
    {
      Operation * op = operations[k];
      // if( lowBoundTime == 0 )
      // lowBoundTime = currentSchedule[op] + op->delay +
      // CPofSubGraph[op];
      // else
      lowBoundTime =
        max(lowBoundTime, currentSchedule[op] + CPofSubGraph[op]);
    }

  for(int k = op->id + 1; k <= h; k++)
    {
      Operation * opk = operations[k];
      set < Operation * >setOfImmediatePrecedent =
        immediatePrecedentOperations[opk];

      for(set < Operation * >::const_iterator it =
            setOfImmediatePrecedent.begin();
          it != setOfImmediatePrecedent.end(); it++)
        {
          Operation * op = (*it);
          temp = currentSchedule[op] + op->delay;
          start[opk] = max(temp, start[opk]);
        }
    }

  // int r = 0;
  /*
   *
   for( int k = op->id + 1; k <= h; k++ )
   {
   Operation * opk =
   * operations[k];
   r = max( optimalSchedule[opk], start[opk] + 1
   * );
   // r = start[opk] + 1;
   lowBoundTime = max( lowBoundTime, r
   * + CPofSubGraph[opk] );
   }
   */
  for(int i = op->id + 1; i <= operations.size(); i++)
    {
      int k = 0;

      for(int k = operations[i]->ASAP; k <= operations[i]->ALAP; k++)
        {
          if(isPrecedence(operations[i], k))
            {
              // only occupy, no release is needed
              currentSchedule[operations[i]] = k;
              occupyResource(k, operations[i]->t, operations[i]->delay);
              break;
            }
        }

      //      k =
      //          max( currentSchedule[operations[i]], start[operations[i]] + 1 );
      lowBoundTime =
        max(lowBoundTime, k  + CPofSubGraph[operations[i]]);
    }

  resources = resources_;
  currentSchedule = tempSchedule;
  FuncTimer::checkout(lowbound_t);
  // printf("low: %d\n", lowBoundTime);
  // if(lowBoundTime == optimalScheduleTime)
  // printf("*\n");
  return lowBoundTime;
}
int
lowBound(int core, Operation * op)
{
  map < type, map < int, int > >resources_ = resources_p[core];
  map < Operation *, int >tempSchedule = currentSchedule_p[core];
  int endid = 0;

  if(op == NULL)
    endid = 0;
  else
    endid = op->id - 1;

  FuncTimer::checkin(lowbound_t);
  int lowBoundTime = 0;
  int temp = 0;
  map < Operation *, int >start;
  multiset < Operation > L_;
  map < int, int >L_array;
  map < int, int >S_;
  int w_ = 0;

  for(int i = 1; i <= endid; i++)
    {
      Operation * op = operations[i]->sortedOp;
      lowBoundTime =
        max(lowBoundTime,
            currentSchedule_p[core][op] + CPofSubGraph[op]);
    }

  /*
   if(op!=NULL)
   {
   int l = *level_l_h[op->level].begin();
   int h = *level_l_h[op->level].rbegin();
   for( int k = endid + 1; k <= h; k++ )
   {
   Operation * opk = operations[k];
   set < Operation * >setOfImmediatePrecedent =
   immediatePrecedentOperations[opk];
   for( set < Operation * >::const_iterator it =
   setOfImmediatePrecedent.begin();
   it != setOfImmediatePrecedent.end(); it++ )
   {
   Operation * op = ( *it );
   temp = currentSchedule_p[core][op] + op->delay;
   start[opk] = max( temp, start[opk] );
   }
   }
   }
   */
  int maxid = 0;

  for(int i = endid + 1; i <= operations.size(); i++)
    {
      int opid = operations[i]->sortedOp->id;
      int k = 0;

      if(op == NULL)
        k = ASAPofMultiThread[core][operations[opid]];//, ASAPUC[operations[opid]]);
      else
        k = ASAPofMultiThread[core][operations[opid]];//, ASAPUC[operations[opid]]);

      //int k = operations[opid]->ASAP;
      //	int k = 1;
      while(true)
        //       for( int k = ASAPofMultiThread[core][operations[opid]];
        //               k <= operations[opid]->ALAP; k++ )
        {
          // only occupy, no release is needed
          if(isResourceAvailable(core, k,
                                 operations[opid]->t,
                                 operations[opid]->delay)
              //                    isPrecedence( core, operations[i], k )
            )
            {
              currentSchedule_p[core][operations[opid]] = k;
              occupyResource(core, k, operations[opid]->t,
                             operations[opid]->delay);
              break;
            }

          k++;
        }

      //     k =
      //         max( currentSchedule_p[core][operations[opid]],
      //              start[operations[opid]] + 1 );
      //               printf("id: %d t:%d asap: %d cp:%d k:%d sum: %d\n", opid, operations[opid]->t, operations[opid]->ASAP,CPofSubGraph[operations[opid]], k, k + CPofSubGraph[operations[opid]]);
      lowBoundTime =
        max(lowBoundTime, k + CPofSubGraph[operations[opid]]);
    }

  resources_p[core] = resources_;
  currentSchedule_p[core] = tempSchedule;
  return lowBoundTime;
}
// get all immediate precedent operations
set < Operation * >getImmediatePrecedent(Operation * op)
{
  set < Operation * >rs;

  for(set < Dependency * >::const_iterator it =
        dependencies.begin(); it != dependencies.end(); it++)
    {
      if((*it)->sink == op)
        {
          Operation * op = (*it)->source;
          rs.insert(op);
        }
    }

  return rs;
}
// determine whether resource of specified type is available
bool isResourceAvailable(int step, type t, int delay)
{
  FuncTimer::checkin(isResourceAvailable_t);

  //    if( resources[t].size() == 0 )
  //        resources[t].clear();
  for(int i = step; i < step + delay; i++)
    {
      // occupy the for subsequent steps
      if(resources[t][i] >= resourcePool[t])
        {
          FuncTimer::checkout(isResourceAvailable_t);
          return false;
        }
    }

  FuncTimer::checkout(isResourceAvailable_t);
  return true;
}
bool isResourceEqual(int core, int step, type t, int delay)
{
  FuncTimer::checkin(isResourceAvailable_t);

  //    if( resources_p[core][t].size() == 0 )
  //        resources_p[core][t].clear();
  for(int i = step; i < step + delay; i++)
    {
      // occupy the for subsequent steps
      if(resources_p[core][t][i] + 1 != resourcePool[t])
        {
          FuncTimer::checkout(isResourceAvailable_t);
          return false;
        }
    }

  FuncTimer::checkout(isResourceAvailable_t);
  return true;
}
bool isResourceAvailable(int core, int step, type t, int delay)
{
  FuncTimer::checkin(isResourceAvailable_t);

  //    if( resources_p[core][t].size() == 0 )
  //        resources_p[core][t].clear();
  for(int i = step; i < step + delay; i++)
    {
      // occupy the for subsequent steps
      if(resources_p[core][t][i] >= resourcePool[t])
        {
          FuncTimer::checkout(isResourceAvailable_t);
          return false;
        }
    }

  FuncTimer::checkout(isResourceAvailable_t);
  return true;
}
bool isPrecedence(Operation * op, int step, map < int, int >schedule)
{
  FuncTimer::checkin(isPrecedence_t);
  bool rs = true;
  set < Operation * >setOfImmediatePrecedent =
    immediatePrecedentOperations[op];

  for(set < Operation * >::const_iterator it =
        setOfImmediatePrecedent.begin();
      it != setOfImmediatePrecedent.end(); it++)
    {
      Operation * op = (*it);
      rs = rs & (schedule[op->id] + op->delay <= step);

      if(rs == false)
        {
          FuncTimer::checkout(isPrecedence_t);
          return rs;
        }
    }

  /*
   *
   for( set<Dependency*>::const_iterator it =
   * dependencies.begin(); it != dependencies.end(); it++ )
   {
   if(
   * ( *it )->sink == op )
   {
   Operation * op = ( *it )->source;
   rs
   * = rs & ( currentSchedule[op] + op->delay <= step );
   if( rs
   * == false )
   return rs;
   }
   }
   */
  FuncTimer::checkout(isPrecedence_t);
  return rs;
}
// determine whether the precedent operations has finished
bool isPrecedence(Operation * op, int step)
{
  FuncTimer::checkin(isPrecedence_t);
  bool rs = true;
  set < Operation * >setOfImmediatePrecedent =
    immediatePrecedentOperations[op];

  for(set < Operation * >::const_iterator it =
        setOfImmediatePrecedent.begin();
      //    printf("op%d have %d precedences\n", op->id, op->precedent.size());
      //    for( set < Operation * >::const_iterator it =
      //        op->precedent.begin();
      it != setOfImmediatePrecedent.end(); it++)
    {
      Operation * op = (*it);
      rs = rs & (currentSchedule[op] + op->delay - 1 < step);

      if(!rs)
        {
          FuncTimer::checkout(isPrecedence_t);
          return rs;
        }
    }

  /*
   *
   for( set<Dependency*>::const_iterator it =
   * dependencies.begin(); it != dependencies.end(); it++ )
   {
   if(
   * ( *it )->sink == op )
   {
   Operation * op = ( *it )->source;
   rs
   * = rs & ( currentSchedule[op] + op->delay <= step );
   if( rs
   * == false )
   return rs;
   }
   }
   */
  FuncTimer::checkout(isPrecedence_t);
  return rs;
}
bool isPrecedence(int core, Operation * op, int step)
{
  FuncTimer::checkin(isPrecedence_t);
  bool rs = true;
  set < Operation * >setOfImmediatePrecedent =
    immediatePrecedentOperations[op];

  for(set < Operation * >::const_iterator it =
        setOfImmediatePrecedent.begin();
      it != setOfImmediatePrecedent.end(); it++)
    {
      Operation * op = (*it);
      //     if( currentSchedule_p[core][op] == 0 )
      //        return false;
      rs = rs & (currentSchedule_p[core][op] + op->delay - 1 < step);

      if(rs == false)
        {
          FuncTimer::checkout(isPrecedence_t);
          return rs;
        }
    }

  FuncTimer::checkout(isPrecedence_t);
  return rs;
}
set < Operation * >getSuccessor(Operation * op)
{
  set < Operation * >rs;
  Graph * subGraph = getSubGraph(op);

  for(set < Operation * >::const_iterator it =
        subGraph->operations.begin();
      it != subGraph->operations.end(); it++)
    {
      rs.insert((*it));
    }

  rs.erase(op);
  return rs;
}
// initialize data structures of the given DFG
void
initDFG()
{
  // get all sink operations and source operations of the DFG
  for(map < int, Operation * >::const_iterator it =
        operations.begin(); it != operations.end(); it++)
    {
      Operation * op = (*it).second;
      sinkOperations.insert(op);
      sourceOperations.insert(op);
    }

  for(set < Dependency * >::const_iterator it =
        dependencies.begin(); it != dependencies.end(); it++)
    {
      Dependency * dep = (*it);
      sinkOperations.erase(dep->source);
      sourceOperations.erase(dep->sink);
    }

  // calculate level
  // printf( "Calculating level for ops...\n" );
  // for( set<Operation*>::const_iterator it =
  // sourceOperations.begin(); it != sourceOperations.end(); it++ )
  // {
  // Operation * op = ( *it );
  // DFS( op, 0 );
  // }
  // longest path algorithm
  floydWarshall();
  printf("Initializing CP...\n");
  CPofSubGraph.clear();
  CPofPredGraph.clear();
  CPofPreRevGraph.clear();
  CPofPredGraph_.clear();

  for(multiset<Operation>::const_iterator it = topoSet.begin(); it != topoSet.end(); it++)
    {
      //       printf ("Processing op %d of %d\n", i, operations.size ());
      Operation * op = operations[it->id];
      CPofSubGraph[op] =
        getCriticalPathLength(op, getSubGraph(op), cpofsub);
      CPofPredGraph[op] =
        getCriticalPathLength(op, getPrecedenceGraph(op), cpofpred);
      CPofPredGraph_[op] = getCriticalPathLength(op, getPrecedenceGraph(op), cpofpred_);
      CPofPreRevGraph[op] =
        getCriticalPathLength(op, getPrecedenceGraph
                              (op,
                               getReversedGraph(getSubGraph(op))),
                              cpofpredresv);
      //    level_l_h[CPofPredGraph_[op]].insert( op->id );
      //    level_count = max( level_count, CPofPredGraph_[op] );
    }

  printf("Initializing Immediate Precedent...\n");

  for(int i = 1; i <= operations.size(); i++)
    {
      Operation * op = operations[i];
      immediatePrecedentOperations[op] = getImmediatePrecedent(op);
    }

  printf("Initializing Successors...\n");

  for(int i = 1; i <= operations.size(); i++)
    {
      Operation * op = operations[i];
      successorOperations[op] = getSuccessor(op);
    }

  printf("Initializing ASAP...\n");
  initASAP();
}
void
getBadSchedule()
{
  int step = 1;

  for(int i = 1; i <= operations.size(); i++)
    {
      currentSchedule[operations[i]] = optimalSchedule[operations[i]] =
                                         badSchedule[operations[i]] = step;
      step += operations[i]->delay;
    }

  optimalScheduleTime = badScheduleTime = w = step;
  fout << "bad schedule: " << step << "\n";
}
void
preEnumaration()
{
  resources.clear();
  //	basicEnu( 1 );
  //	resources.clear();
  printf("Listing...\n");
  currentSchedule.clear();
  listingSchedule.clear();
  resources.clear();

  srand((unsigned)time(0));

  //for(int i=0;i<100;i++)
  {
    listSchedule(byasap);
    int list1 = listSchedulingTime;
    optimalScheduleTime = w = list1;
    optimalSchedule = listingSchedule;
    listSchedule(byalap);
    int list2 = listSchedulingTime;

    if(list1 > list2)
      {
        global_listorder = byalap;
        optimalScheduleTime = w = listSchedulingTime = list2;
        optimalSchedule = listingSchedule;
      }
    else
      {
        global_listorder = byasap;
        optimalScheduleTime = w = listSchedulingTime = list1;
        optimalSchedule = listingSchedule = optimalSchedule;
      }
  }

  // global_listorder = byasap;

  // getBadSchedule();
  printf("Initializing ALAP...\n");
  initALAP();
  sortedSetByALAP.clear();

  for(int i = 1; i <= operations.size(); i++)
    {
      //		operations[i]->sort_id = -operations[i]->ASAP ;
      operations[i]->sort_id = -operations[i]->ASAP;
      sortedSetByALAP.insert(*operations[i]);
    }

  writeSchedule("ALAP");

  new_low = compute_lower_bound();
  fout << "\nglobal low: " << globalLow << " new low: " << new_low << "\n";
  printf("new low: %d\n", new_low);
}
// initialize best schedule and best schedule time
void
initOptimalSchedule()
{
  for(map < int, Operation * >::const_iterator it =
        operations.begin(); it != operations.end(); it++)
    {
      Operation * op = (*it).second;
      optimalSchedule[op] = op->id;
    }

  optimalScheduleTime = w = 20;
}
// give a feasible list schedule and w
void
listSchedule()
{
  map < type, map < int, int > >resources_ = resources;
  multiset < Operation > L_;
  map < int, int >L_array;
  int w_ = 0;

  for(int i = 1; i <= operations.size(); i++)
    {
      // printf( "listSchedule: processing op %d...\n", i );
      operations[i]->sort_id = -operations[i]->ASAP;// CPofSubGraph[operations[i]];
      //operations[i]->sort_id = -operations[i]->id;
      L_.insert(*operations[i]);
    }

  int count = 1;

  for(multiset < Operation >::iterator it = L_.begin();
      it != L_.end(); it++)
    {
      L_array[count] = (*it).id;
      count++;
    }

  //    for( int l = operations[L_array[1]]->ASAP; l <= operations[L_array[1]]->ASAP + 10; l++ )
  //    {
  //        resources = resources_;

  for(int k = 1; k <= operations.size(); k++)
    {

      Operation * opk = operations[L_array[k]];
      printf("list sequence: op%d with cp%d\n", L_array[k], CPofSubGraph[opk]);
      int j =  opk->ASAP;

      while(true)
        {
          //     printf( "listSchedule: stepping op %d...\n", j );
          if(isPrecedence(opk, j)
              && isResourceAvailable(j, opk->t, opk->delay))
            {
              // only occupy, no release is needed
              occupyResource(j, opk->t, opk->delay);
              listingSchedule[opk] = currentSchedule[opk] = j;
              break;
            }

          j++;
        }
    }

  for(int m = 1; m <= operations.size(); m++)
    {
      Operation * op = operations[L_array[m]];
      w_ = max(listingSchedule[op] + op->delay - 1, w_);
    }

  listSchedulingTime = w_;
  optimalScheduleTime = w = min(w, w_);
  //printf("list length: %d\n", listSchedulingTime);
  //        l++;
  //    }
  // restore resource usage pool
  resources = resources_;
}

void
listSchedule(listorder lo)
{
  float magic = 0;
  map < type, map < int, int > >resources_ = resources;
  multiset < Operation > L_;
  map < int, int >L_array;
  int w_ = 0;

  for(int i = 1; i <= operations.size(); i++)
    {
      magic = 0;//rand()/((double)RAND_MAX+0.5);

      //   printf("magic: %f\n", magic);
      // printf( "listSchedule: processing op %d...\n", i );
      switch(lo)
        {
        case byasap:

          operations[i]->sort_id = -operations[i]->ASAP - magic;
          break;
        case byalap:
          operations[i]->sort_id = CPofSubGraph[operations[i]] - magic;
          break;

        default:
          break;
        }

      L_.insert(*operations[i]);
    }

  int count = 1;

  for(multiset < Operation >::iterator it = L_.begin();
      it != L_.end(); it++)
    {
      L_array[count] = (*it).id;
      count++;
    }

  //    for( int l = operations[L_array[1]]->ASAP; l <= operations[L_array[1]]->ASAP + 10; l++ )
  //    {
  //        resources = resources_;

  for(int k = 1; k <= operations.size(); k++)
    {

      Operation * opk = operations[L_array[k]];
      //   printf("list sequence: op%d with cp%d\n",L_array[k], CPofSubGraph[opk] );
      int j =  opk->ASAP;

      while(true)
        {
          //     printf( "listSchedule: stepping op %d...\n", j );
          if(isPrecedence(opk, j)
              && isResourceAvailable(j, opk->t, opk->delay))
            {
              // only occupy, no release is needed
              occupyResource(j, opk->t, opk->delay);
              listingSchedule[opk] = currentSchedule[opk] = j;
              break;
            }

          j++;
        }
    }

  for(int m = 1; m <= operations.size(); m++)
    {
      Operation * op = operations[L_array[m]];
      w_ = max(listingSchedule[op] + op->delay - 1, w_);
    }

  listSchedulingTime = w_;
  //optimalScheduleTime = w = min( w, w_ );
  // printf("list length: %d\n", listSchedulingTime);
  //        l++;
  //    }
  // restore resource usage pool
  resources = resources_;
}

void resetContext()
{
  resources.clear();
  completeBranchBound = false;
  total_traverse = 0;
  maxOpTraversed = 0;
  optimalScheduleTime = w = listSchedulingTime;
  currentSchedule = optimalSchedule = listingSchedule;
  FuncTimer::init();
  currentSchedule_p[1] = optimalSchedule;
  optimalSchedule_p[1] = optimalSchedule;
  resources_p.clear();
  resource_snapshot_p.clear();

  for(map < int, Operation * >::const_iterator it =
        operations.begin(); it != operations.end(); it++)
    ASAPofMultiThread[1][(*it).second] = (*it).second->ASAP;

  for(map < int, Operation * >::const_iterator it =
        operations.begin(); it != operations.end(); it++)
    ALAPofMultiThread[1][(*it).second] = (*it).second->ALAP;
}
void
printResult(fstream * fout)
{
  *fout << "The optimal schedule time is " << optimalScheduleTime <<
        "\n";

  for(map < Operation *, int >::const_iterator it =
        optimalSchedule.begin(); it != optimalSchedule.end(); it++)
    {
      Operation * op = (*it).first;
      int step = (*it).second;
      *fout << op->id << "\t" << optimalSchedule[op] << "\n";
    }

  *fout << "Finished branchbound? " << completeBranchBound << "\n";
}
void parallelTestDriver(void * arg)
{
  resetContext();
  parallel_ag * pa = (parallel_ag*)arg;
  core_number = pa->core_limit;
  char info[256];
  sprintf(info, "using %d core(s) to perform...\n", core_number);
  printInfo(info);
  //pa->assignmentSemaphore = CreateSemaphore( NULL, 1, 1, NULL );
  sem_init(&pa->assignmentSemaphore, 1, 1);

  for(int i = 1; i <= assignment; i++)
    pa->assignmentMap.insert(i);

  for(int i = 1; i <= core_number; i++)
    {
      currentSchedule_p[i] = basicSchedule;
      optimalSchedule_p[i] = basicSchedule;
      resources_p[i].clear();
      resource_snapshot_p[i].clear();

      for(map < int, Operation * >::const_iterator it =
            operations.begin(); it != operations.end(); it++)
        {
          //   printf("ASAPofMultiThread[%d] = %d\n", i,  ( *it ).second->ASAP);
          ASAPofMultiThread[i][(*it).second] = (*it).second->ASAP;
        }
    }

  long branch_with_parallel_start = GetTickCount();
  long branch_with_parallel_end = 0;
  long branch_with_parallel_duration = 0;
  int count = 0;

  while(branch_with_parallel_duration < 10)
    {


      for(int i = 1; i <= core_number; i++)
        {
          thread_ag * ta = (thread_ag *) malloc(sizeof(thread_ag));

          if(core_number >= assignment)
            {
              ta->lower = i;
              ta->upper = i;
            }
          else
            {
              ta->lower =
                (i - 1) * assignment / (unsigned int)(core_number) * 1.0 +
                1;
              ta->upper =
                (i +
                 1) * (assignment / (unsigned int)(core_number)) * 1.0 >
                assignment ? assignment : (i) * assignment /
                (unsigned int)(core_number) * 1.0;
            }

          ta->coreID = i;
          ta->assignmentMap = &pa->assignmentMap;
          ta->assignmentSemaphore = &pa->assignmentSemaphore;
          // threadMap[i] = ( int )_beginthread( coreScheduler, 0, ( void* )ta );//
          printf("started thread on core %d\n", ta->coreID);
          pthread_create(&threadMap[i], NULL, (void * (*)(void*))coreScheduler, (void*)(ta));
          // SetThreadPriority( threadMap[i],
          // THREAD_PRIORITY_HIGHEST );
          // SetThreadAffinityMask( threadMap[i], ( DWORD_PTR
          // )coreNumber );
          // WaitForSingleObject( threadMap[i], INFINITE );



        }

      for(int i = 1; i <= core_number; i++)
        //WaitForSingleObject( threadMap[i], INFINITE );
        pthread_join(threadMap[i], NULL);

      branch_with_parallel_end = GetTickCount();
      branch_with_parallel_duration =
        branch_with_parallel_end - branch_with_parallel_start;
      count++;
    }

  // add_count--;
  // multi_count--;
  // if( add_count == 0 || multi_count == 0 )
  // break;
  // resourcePool[( enum type ) 1] = add_count;
  // resourcePool[( enum type ) 2] = multi_count;
  // listSchedule();
  // initALAP();
  // }
  fout.flush();
  fout << "parallel total duration: " << (branch_with_parallel_duration)
       * 1.0 / count << "with core " << core_number << "\n";
}

void validateSchedule(map<Operation*, int> Schedule, map < type, map < int, int > > resources)
{

}

int compute_lower_bound()
{
  int cp = 0;

  for(set<Operation*>::iterator it = sinkOperations.begin(); it != sinkOperations.end(); it++)
    {
      Operation * op = *it;
      op->asapuc = ASAPUC[op] = compute_asapuc(op);
      cp = max(op->asapuc, cp);
    }

  //  printf("top cp: %d\n", cp);
  compute_alapuc(sinkOperations, cp);
  return(greedy_lower_bound(sinkOperations, cp));

}

// done
int compute_asapuc(Operation* op)
{
  if(sourceOperations.find(op) != sourceOperations.end())
    {
      op->alapuc = 1; // todo: corrent? or op->ALAP;
      return op->ASAP;
    }
  else
    {
      return recursive_lower_bound(op);
    }
}

// done
void compute_alapuc(set<Operation*> R, int CP)
{
  Operation * root;
  set < Operation * > target_nodes;
  int temp_cp;

  for(set < Operation * >::const_iterator it =
        R.begin(); it != R.end(); it++)
    {
      Operation * op = (*it);
      temp_cp = CPofPredGraph[op];
      root = op;
      Graph * subgraph = getPrecedenceGraph(op);

      //    printf("subgraph of op%d contains %d children\n", op->id, subgraph->operations.size());
      for(set<Operation*>::iterator it = subgraph->operations.begin(); it != subgraph->operations.end(); it++)
        {
          Operation * child = *it;
          target_nodes.insert(child);
        }
    }

  //   printf("greedy: target number: %d\n", target_nodes.size());

  map < type, map < int, int > >resources_ = resources_p[1];
  map < Operation *, int >tempSchedule = currentSchedule_p[1];

  resources_p[1].clear();
  currentSchedule_p[1].clear();

  int upperBoundTime = 0;
  int temp = 0;
  map < Operation *, int >start;
  multiset < Operation > L_;
  map < int, int >L_array;
  map < int, int >S_;
  int w_ = 0;

  //   printf("greedy: constrauct L_\n");
  for(set < Operation * >::const_iterator it =
        target_nodes.begin(); it != target_nodes.end(); it++)
    {
      Operation * op = (*it);
      // printf( "listSchedule: processing op %d...\n", i );
      op->sort_id = -op->ALAP;
      //operations[i]->sort_id = -operations[i]->id;
      L_.insert(*op);
    }

  //  printf("greedy: constrauct L_array\n");
  int count = 1;

  for(multiset < Operation >::iterator it = L_.begin();
      it != L_.end(); it++)
    {
      L_array[count] = (*it).id;
      count++;
    }

  int maxid = 0;

  for(int i = 1; i <= target_nodes.size(); i++)
    {
      Operation * op = operations[L_array[i]];
      //       printf("op%d asap:%d asapuc:%d | alap:%d alapuc:%d\n", op->id, op->ASAP, op->asapuc, op->ALAP, op->alapuc);

      int k = op->asapuc;

      while(true)
        {
          // only occupy, no release is needed
          if(isResourceAvailable(1, k,
                                 op->t,
                                 op->delay)
              && isPrecedence(1, op, k)
            )
            {
              currentSchedule_p[1][op] = k;
              occupyResource(1, k, op->t,
                             op->delay);
              break;
            }

          k++;
        }

      upperBoundTime =
        max(upperBoundTime, k + op->delay - 1);
    }

  //  printf("compute_alapuc: upperBoundTime %d, cp %d\n", upperBoundTime, CP);
  if(R.size() == 1)
    {
      //   printf("max gap: %d\n", lowBoundTime);
      for(set < Operation * >::const_iterator it =
            target_nodes.begin(); it != target_nodes.end(); it++)
        {
          Operation * op = (*it);
          // printf( "listSchedule: processing op %d...\n", i );
          //       printf("cpofnoes: from %d to %d:%d\n", op->id, root->id, CPofNodes[op][root]);
          op->alapuc = ALAPUC[op] = upperBoundTime - CPofNodes[op][root] - root->delay + 1;
        }
    }
  else
    {
      for(set < Operation * >::const_iterator it =
            target_nodes.begin(); it != target_nodes.end(); it++)
        {
          Operation * op = (*it);
          // printf( "listSchedule: processing op %d...\n", i );
          //        printf("cpofsubgraph: from %d cp %d\n", op->id, CPofSubGraph[op]);
          op->alapuc = ALAPUC[op] = upperBoundTime - CPofSubGraph[op];
        }
    }


  resources_p[1] = resources_;
  currentSchedule_p[1] = tempSchedule;
}

int greedy_lower_bound(set<Operation*> R, int CP)
{
  //  printf("greedy cp: %d\n", CP);
  set < Operation * > target_nodes;
  Operation * root;

  for(set < Operation * >::const_iterator it =
        R.begin(); it != R.end(); it++)
    {
      Operation * op = (*it);
      root = op;
      Graph * subgraph = getPrecedenceGraph(op);

      //      printf("subgraph of op%d contains %d children\n", op->id, subgraph->operations.size());
      for(set<Operation*>::iterator it = subgraph->operations.begin(); it != subgraph->operations.end(); it++)
        {
          Operation * child = *it;
          target_nodes.insert(child);
        }
    }

  //   printf("greedy: target number: %d\n", target_nodes.size());

  map < type, map < int, int > >resources_ = resources_p[1];
  map < Operation *, int >tempSchedule = currentSchedule_p[1];

  resources_p[1].clear();
  currentSchedule_p[1].clear();

  int lowBoundTime = 0;
  int temp = 0;
  map < Operation *, int >start;
  multiset < Operation > L_;
  map < int, int >L_array;
  map < int, int >S_;
  int w_ = 0;

  //   printf("greedy: constrauct L_\n");
  for(set < Operation * >::const_iterator it =
        target_nodes.begin(); it != target_nodes.end(); it++)
    {
      Operation * op = (*it);
      // printf( "listSchedule: processing op %d...\n", i );
      op->sort_id = -op->ALAP;
      //operations[i]->sort_id = -operations[i]->id;
      L_.insert(*op);
    }

  //   printf("greedy: constrauct L_array\n");
  int count = 1;

  for(multiset < Operation >::iterator it = L_.begin();
      it != L_.end(); it++)
    {
      L_array[count] = (*it).id;
      count++;
    }

  int maxid = 0;

  for(int i = 1; i <= target_nodes.size(); i++)
    {
      Operation * op = operations[L_array[i]];


      int k = op->asapuc;

      while(true)
        {
          // only occupy, no release is needed
          if(isResourceAvailable(1, k,
                                 op->t,
                                 op->delay)
              //                    isPrecedence( core, operations[i], k )
            )
            {
              currentSchedule_p[1][op] = k;
              occupyResource(1, k, op->t,
                             op->delay);
              break;
            }

          k++;
        }


      if(R.size() == 1)
        {
          //        printf("op%d asap:%d asapuc:%d | alap:%d alapuc:%d kstep: %d low:%d\n", op->id, op->ASAP, op->asapuc, op->ALAP, op->alapuc, k, k + CPofNodes[op][root] + root->delay - 1);
          lowBoundTime =
            max(lowBoundTime, k + CPofNodes[op][root]);
        }
      else
        {
          //          printf("op%d asap:%d asapuc:%d | alap:%d alapuc:%d kstep: %d low:%d\n", op->id, op->ASAP, op->asapuc, op->ALAP, op->alapuc, k, k + CPofSubGraph[op]);
          lowBoundTime =
            max(lowBoundTime, k + CPofSubGraph[op]);
        }
    }


  //  printf("max gap: %d\n", lowBoundTime);


  resources_p[1] = resources_;
  currentSchedule_p[1] = tempSchedule;
  return lowBoundTime;
}

// done
int compute_critical_path(Operation* op)
{
  int rs = 0;

  for(set<Operation*>::iterator it = op->precedent.begin(); it != op->precedent.end(); it++)
    {
      Operation * pre = *it;
      rs = max(rs, pre->asapuc + pre->delay - 1);
    }

  return rs;
}

// done
int recursive_lower_bound(Operation* op)
{
  for(set<Operation*>::iterator it = op->precedent.begin(); it != op->precedent.end(); it++)
    {
      Operation * pre = *it;

      //      printf("recur: op%d 's asapuc %d\n", pre->id, pre->asapuc);
      if(pre->asapuc == 0)
        pre->asapuc = ASAPUC[pre] = compute_asapuc(pre);
    }

  int CP = op->asapuc = compute_critical_path(op);
  set<Operation*> nodes;
  nodes.insert(op);
  compute_alapuc(nodes, op->asapuc);
  return(greedy_lower_bound(nodes, CP));
}

int main(int argc, char **argv)
{
  bool config_multithread;
  int config_add;
  int config_multi;
  bool config_multiround;
  const char ConfigFile[] = "config.txt";
  Config configSettings(ConfigFile);
  config_multithread = configSettings.Read("multithread", false);
  config_add = configSettings.Read("add", 0);
  config_multi = configSettings.Read("multi", 0);
  config_multiround = configSettings.Read("multiround", false);
  config_echo = configSettings.Read("echo", false);
  config_low = configSettings.Read("low", false);
  config_level = configSettings.Read("level", false);
  FuncTimer::init();
  ifstream fin2("target.txt");
  string filename;
  fstream latexout;
  latexout.open("latex.txt", ios::out);

  while(getline(fin2, filename))
    {
      ifstream fin3("resource.txt", ios::in);

      while(!fin3.eof())
        {
          int add_number = 0, multi_number = 0;
          fin3 >> add_number >> multi_number;
          char str[256];
          sprintf(str, "process file %s with %d adders and %d multipliers\n", filename.c_str(), add_number, multi_number);
          printInfo(str);
          char rsFileName[256];
          sprintf(rsFileName, "%s_rs_%d%d.txt", filename.c_str(), add_number, multi_number);
          fout.open(rsFileName, ios::out);
          // fstream fin( argv[1], ios::in );
          // fstream fin( "AR_r.txt", ios::in );
          fstream fin(filename.c_str(), ios::in);
          // fout.open( argv[2], ios::out );
          int operation_count,
              constraint_count, add_count, multi_count, add_delay, multi_delay,
              level, graph;
          fin >> operation_count >> constraint_count >> add_count >> multi_count
              >> add_delay >> multi_delay;
          fout << "total operations: " << operation_count << "\n";
          fout << "total constraints: " << constraint_count << "\n";
          add_count = add_number;
          multi_count = multi_number;
          fout << "total adder: " << add_count << "\n";
          fout << "total muliplier: " << multi_count << "\n";
          resourcePool[(enum type) 1] = add_count;
          resourcePool[(enum type) 2] = multi_count;
          printf("Reading from test case file...\n");

          for(int i = 0; i < operation_count; i++)   // serious bug i starts from 1 not 0
            {
              int id, type;
              fin >> id >> type >> level >> graph;
              fout << id << " " << type << "\n";
              Operation * op = new Operation();
              op->base_addr = op;
              op->id = id;                // kritische Frage hier: id oder i?
              op->visited = false;
              op->CPofPreRevGraph = -1;
              op->CPPredGraph = -1;
              op->CPSubGraph = -1;
              op->level = level;
              op->graph = graph;
              graph_count = max(graph_count, graph);

              if(type == add)
                {
                  op->t = add;
                  op->delay = add_delay;
                }
              else if(type == multiplication)
                {
                  op->t = multiplication;
                  op->delay = multi_delay;
                }

              operations[id] = op;
            }

          for(int i = 0; i < constraint_count; i++)
            {
              int id, source, sink;
              fin >> source >> sink;
              fout << i << " " << source << " " << sink << "\n";
              Dependency * dep = new Dependency();
              dep->id = i;
              dep->sink = operations[sink];
              dep->source = operations[source];
              dependencies.insert(dep);
              operations[source]->adj.insert(dep);
              operations[sink]->in.insert(dep);
              operations[source]->children.insert(operations[sink]);
              operations[sink]->precedent.insert(operations[source]);
            }

          // invoke the algorithm
          topoSort();
          initDFG();
          // while( add_count != 0 && multi_count != 0 )
          // {
          preEnumaration();

          if(true)
            {
              int count = 1;

              for(multiset < Operation >::iterator it = sortedSetByALAP.begin();
                  it != sortedSetByALAP.end(); it++)
                {
                  operations[count]->sortedOp = operations[(*it).id];
                  count++;
                  endofLevel[(*it).level] = (*it).id;
                }
            }

          fout << "++++++++++++++++++++++++++\n";
          fout << "current adder: " << add_count << "\n";
          fout << "current muliplier: " << multi_count << "\n";
          printf("Estimated space: %d\n", getEstimatedSpace());
          fout << "Estimated space: " << getEstimatedSpace() << " \n";
          fout << "\nList scheduling\n";
          fout << "The list schedule time is " << listSchedulingTime << "\n";

          for(int i = 1; i <= operations.size(); i++)
            {
              Operation * op = operations[i];
              fout << op->id << "\t" << listingSchedule[op] << " " << op->
                   ASAP << " " << op->ALAP << " " << op->asapuc
                   << " " << op->alapuc << "\n";
            }

          fout.flush();
          resetContext();

          latex_global = globalLow = lowBound(1, NULL);
          printf("global low: %d\n", globalLow);
          latex_global = globalLow = max(new_low , globalLow);

          //     testDriver( "composite", true, true, true, false );
          //     testDriver( "bulb", false, false, false, false );

          fout.flush();

          // test multi thread
          if(config_multithread)
            {
              printf("start parallel algorithm...\n");
              assignment = operations[1]->ALAP;
              map<int, pthread_t> parallelSet;//

              for(int core_count = 4; core_count <= 4; core_count = core_count * 2)
                {
                  parallel_ag pa;
                  pa.core_limit = core_count;
                  pa.assignmentMap.clear();
                  printf("starting parallelSet %d\n", core_count);
                  //             parallelSet[core_count] = ( int* )_beginthread( parallelTestDriver, NULL, ( void* )&pa );
                  //WaitForSingleObject( parallelSet[core_count], INFINITE );
                  pthread_create(&parallelSet[core_count], NULL, (void * (*)(void*))parallelTestDriver, (void*)&pa);
                  pthread_join(parallelSet[core_count], NULL);

                  //                    parallelSet[core_count] = t;

                }
            }

          // test multi thread ==
          printf("Finished...\n");
          fout << "-------------------------------------------\n";
          fout.flush();
          fout.close();
        }
    }

  for(int l = 0; l < history_level_info.size(); l++)
    {
      if(history_level_info[l] != NULL)
        delete history_level_info[l];// = new vector<int>();
    }

  // check the correctness of the found optimal scheduling
  resources_p.clear();
  currentSchedule_p[1].clear();

  for(int i = 1; i <= operations.size(); i++)
    {

      Operation * op = operations[i]->sortedOp;
      int step = optimalSchedule_p[1][op];
      printf("checking op%d at step %d\n", op->id, step);

      if(!isResourceAvailable(1, step, op->t, op->delay))
        printf("wrong scheduling due to resource conflict at step %d of op %d\n", step, op->id);

      if(!isPrecedence(1, op, step))
        printf("wrong scheduling due to precedent conflict at step %d of op %d\n", step, op->id);

      currentSchedule_p[1][op] = step;
      occupyResource(1, step, op->t, op->delay);
    }

  latexout.flush();
  latexout.close();
  fin2.close();
  return 0;
}
